%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}
\usepackage{pgfplots}
%\pgfplotsset{width=10cm,compat=1.9}
%\usepgfplotslibrary{external}
%
%\tikzexternalize
%



\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{Expérimentation sur GAC, MaxRPWC1, MaxRPWC3, rPIC, RPWC} % The short title appears at the bottom of every slide, the full title is only on the title page
\vspace{0.2cm}
\vspace{0.2cm}
\author{
Etudiant: KHONG Minh Thanh\\
Superviseurs: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------
%
%%------------------------------------------------
%\section{MaxRPWC1} 
%%------------------------------------------------
%\begin{frame}[fragile]
%\frametitle{Max-RPWC-1}
%Algorithme MaxRPWC1 \cite{domain:2008} 
%\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
%function Revise($x_j, c_i,MaxRPWC$)
%   for each value $a \in D(x_j)$
%      PW $\leftarrow$ FALSE;
%      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
%         PW $\leftarrow$ TRUE;
%         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
%            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
%               PW $\leftarrow$ FALSE; break;
%         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
%      if PW = FALSE remove $a$ from $D(x_j)$;
%   return number of deleted values;
%\end{lstlisting}
%{\footnotesize
%Ligne 4-10 : pour chaque valide tuple $\tau \in rel(c_m), \tau[x_j]=a$, tester s'il peut étendre aux autres contraintes intersectées avec $c_i$. Si non, enlever $a$ de $D(x_j)$.\\
%Ligne 6-7 : pour chaque contrainte $c_m$, tester si $\tau$ a PW-support $\tau'$ dans $c_m$.\\
%Complexité : time : $O(e^2k^2d^p)$, space : $O(ekd)$, p : maximum nombre de variables dans deux contraintes intersectées
%
%}
%\end{frame}

%------------------------------------------------

%%------------------------------------------------
%\section{MaxRPWC}
%%------------------------------------------------
%%------------------------------------------------
%\section{Implémentation}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Implémentation}
%Il y a deux classes principale à faire :
%\begin{itemize}
%\item MaxRPWC3 : 
%	\begin{itemize}
%	\item appeler la propagation 
%	\item trouver les intersections entre les contraintes
%	\end{itemize}
%\item ConstraintHardExtensionRPWC3 :
%	\begin{itemize}
%	\item contenir la méthode "runPropagator(Variable)" qui fait la fonction "Revise($x_j, c_i,MaxRPWC$)" pour réviser la consistance des variables de la contrainte
%	\end{itemize}
%\end{itemize}
%\end{frame}
%
%%------------------------------------------------
%
%\begin{frame}[fragile]
%\frametitle{Implémentation}
%Implémentation de la méthode "runPropagator(Variable)" :
%\begin{lstlisting}[caption=function runPropagator(Variable)]
%ConstraintHardExtensionRPWC3.runPropagator(Variable)
%   // $c_i$ is this constraint
%   for each variable $x_j \in c_i$ 
%      Revise($x_j, c_i,MaxRPWC$)
%   // update domain of all variable in $c_i$, return false if a domain of variable is empty   
%   return updateDomain()
%\end{lstlisting}
%\begin{itemize}
%\item Problème : 
%Ne pas implémenter $lastGAC_{x_j,a,c_i}$ à cause du changement des indexes des tuples, on doit donc chaque fois parcourir au début des tuples.
%\item Modification : 
%Enlever les tuples qui ne peut pas étendre aux autres tuples dans la fonction "Revise($x_j, c_i,MaxRPWC$)", il diminue les tuples à parcourir chaque fois
%\end{itemize}
%\end{frame}

%------------------------------------------------
\section{Expérimentation}
%------------------------------------------------
\begin{frame}
\frametitle{Expérimentation}
\begin{itemize}
\item L'expérimentation est lancé sur un PC de 4GB RAM, Core i5-2520M, Ubuntu. 
\item Le problèmes utilisés sont renault, random, random-fcd dans \cite{problem}. Le nombre de variable intersecté est 2-10.
\item Les consistances à tester sont GAC(algo STR2), MaxRPWC1, MaxRPWC3, rPIC, RPWC, PWC.
\item Les critères à considérer sont CPU time(s), et node.
\end{itemize}
\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
\small{
Le résultat (CPU time(s), node) :}
\begin{center}
\scalebox{0.75}{
    \begin{tabular}{ | l | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
    \hline
    Problème  & GAC        & RPWC 		& rPIC 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    renault-0 & \textbf{0.53}, 156  & 3.06, 114 	& 12.62, \textbf{111} & 14.16, \textbf{111} & 17.77, \textbf{111} & 3.40, \textbf{111}\\ \hline
    renault-1 & \textbf{0.70}, 972  & 33.44, 1013& 71.16, 556 & 37.83, 195 & 31.35, 195 & 1.95, \textbf{0}\\ \hline
    renault-2 & \textbf{0.69}, \textbf{111}  & 1.65, \textbf{111}	& 10.34, \textbf{111}& 12.84, \textbf{111} & 14.33, \textbf{111} & 3.21, \textbf{111}\\ \hline
    renault-3 & \textbf{0.88}, 1121 & 34.37, 1347 & 78.13, 1215 & 79.74, 1036 & 36.77, 1036 & 2.45, \textbf{0}\\ \hline
    renault-4 & \textbf{0.80}, 114  & 1.64, \textbf{112} 	& 7.96, \textbf{112} & 11.71, \textbf{112} & 16.82, \textbf{112} & 2.29, \textbf{112}\\ \hline
    renault-5 & \textbf{1.00}, 1299 & 42.99, 1409& 92.45, 1263 &  64.31, 1341 & 46.22, 1341 & 1.81, \textbf{0} \\ \hline
    renault-6 & \textbf{1.08}, 1379 & 25.01, \textbf{1199}& 56.58, 1307 & 43.92, 1324 & 35.07, 1324  & 5.02, 1256\\ \hline
    renault-7 & \textbf{0.93}, 141  & 2.50, 119 	& 12.07, 116&  12.37, 113 & 12.62, 113 & 2.63, \textbf{112}\\ \hline
    renault-8 & \textbf{0.82}, 1124 & 25.81, 1124 & 73.39, 1094 &  56.34, 963 & 36.43, 963 & 1.99, \textbf{0}\\ \hline
    \end{tabular}
}
\end{center}
\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
\small{
Le résultat (CPU time(s), node) :}
\begin{center}
\scalebox{0.50}{
    \begin{tabular}{ | p{3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
    \hline
    Problème  & GAC        & RPWC 		& rPIC 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    rand-3-20-20-60-632-fcd-12\_ext & 182.90, 442618  & -, - 	& -, - & -, - & -, - & 235.41, 141422\\ \hline
    rand-3-20-20-60-632-fcd-13\_ext & 89.34, 291047  & 1627.96, 184029 	& -, -  & -, - & 880.19, 119516 & 74.86, 111347\\ \hline
    rand-3-20-20-60-632-fcd-22\_ext & 176.08, 357888  & 1538.05, 205691 	& -, - & -, - & -, - & 166.37, 121615\\ \hline
    rand-3-20-20-60-632-fcd-25\_ext & 65.04, 162524  & 680.60, 84636 	& -, - & 1911.18, 57987 & 477.93, 57930 & 62.12, 57883\\ \hline
    rand-3-20-20-60-632-fcd-26\_ext & 94.68, 314612  & 616.62, 104954 	& -, - & 1046.79, 28009 & 278.88, 25027 & 24.30, 20203\\ \hline
    rand-3-20-20-60-632-fcd-27\_ext & 169.17, 447726  & 1835.56, 251913 	& -, - & -, - & 1884.4, 119917 & 147.66, 111419\\ \hline
    rand-3-20-20-60-632-fcd-2\_ext & 30.49, 69199  & 225.20, 36131 	& 1111.33, 30128 & 1026.40, 22830 & 266.94, 20969 & 35.57, 18248\\ \hline
    rand-3-20-20-60-632-fcd-31\_ext & 88.56, 253745  & 559.61, 111407 & -, - & -, - & 682.56, 79625 & 72.83, 77716\\ \hline
    rand-3-20-20-60-632-fcd-32\_ext & 91.07, 233802  & 1296.33, 155292 	& -, - & -, - & 1484.07, 95792 & 100.09, 84892\\ \hline
    rand-3-20-20-60-632-fcd-33\_ext & 239.85, 724656  & -, - 	& -, - & -, - & 618.86, 87906 & 195.73, 206415\\ \hline
    rand-3-20-20-60-632-fcd-34\_ext & 68.79, 206031  &  840.33, 122238	& -, - & -, - & 984.49, 67087 & 62.45, 57367\\ \hline
    rand-3-20-20-60-632-fcd-35\_ext & 9.21, 23546  & 84.60, 12079	& 457.52, 10542 & 384.65, 6914 & 97.88, 6190 & 6.76, 5165\\ \hline
    rand-3-20-20-60-632-fcd-39\_ext & 48.75, 146557  & 808.11, 76763 	& -, - & 1515.00, 27827 & 309.43, 26320 & 39.09, 27524\\ \hline
    rand-3-20-20-60-632-fcd-3\_ext & 57.39, 157061  & 725.5, 90875	& -, - & -, - & 466.60, 62442 & 69.71, 58492 \\ \hline
    rand-3-20-20-60-632-fcd-40\_ext & 105.05, 252077  & 1119.37, 124814 	& -, - & -, - & 953.09, 70151 & 89.41, 65002\\ \hline
    rand-3-20-20-60-632-fcd-50\_ext & 373.71, 1263148  & -, - 	& -, - & -, - & -, - & 198.65, 192628\\ \hline
    \end{tabular}
}
\end{center}
\end{frame}


\begin{frame}
\frametitle{Expérimentation}

\begin{table}[h]
\begin{center}
\scalebox{0.5}{
    \begin{tabular}{ | p{2cm} | p{0.3cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} | p{1.8cm} |}
    \hline
    Problème  & & GAC (STR2)  	& RPWC1 		& rPIC1 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    dubois-100 & t n & -, -  & -, - & -, - & -, - & -, - & -, -\\ \hline
    dubois-20 & t n & 23.07, 25690106  & 19.30, 2621434& 12.28, 2621434 & 12.13, 2621434 & 12.15, 2621434 & 15.56, 19398612\\ \hline
    dubois-21 & t n & 68.69, 53477370  & 36.34, 5242874& 24.56, 5242874 & 29.22, 5242874 & 24.72, 5242874 & 37.26, 40370130\\ \hline
    dubois-22 & t n & 112.93, 111149050  & 66.81, 10485754 & 51.58, 10485754 & 56.56, 10485754 & 55.54, 10485754 & 77.28, 83886032\\ \hline
    dubois-23 & t n & 223.71, 230686714  & 149.52, 20971514 & 124.77, 20971514 & 101.01, 20971514 & 156.90, 20971514 & 177.85, 174063566\\ \hline
    dubois-24 & t n & 494.19, 478150650  & 330.38, 41943034 & 221.39, 41943034 & 203.98, 41943034 & 276.17, 41943034 & 356.77, 360710092\\ \hline
    dubois-25 & t n & 1099.33, 989855738  & 626.14, 83886074& 542.38, 83886074 & 410.77, 83886074 & 529.80, 83886074 & 710.21, 746586058\\ \hline
    dubois-26 & t n & -, -  & 1511.64, 167772154 & 1197.05, 167772154 & 862.41, 167772154 & 1086.80, 167772154 & 1585.99, 1543503816\\ \hline
    dubois-27 & t n & -, -  & -, -	& -, - & 1786.85, 335544314 & -, - & -, -\\ \hline
    dubois-28 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
    dubois-29 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
    dubois-30 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
    dubois-50 & t n & -, -  & -, - 	& -, - & -, - & -, - & -, -\\ \hline
    \end{tabular}
}
\end{center}
\caption{Résultat expérimental sur les instances du problème \textit{dubois}}
\label{table:dubois}
\end{table}
\end{frame}



%%------------------------------------------------
%%
%\begin{frame}
%\frametitle{Expérimentation}
%
%\begin{tikzpicture} 
%\begin{loglogaxis}[ xlabel={renault instance}, ylabel={Temps d'exécution(s)} ] 
%\addplot coordinates { (5,8.312e-02) (17,2.547e-02) (49,7.407e-03) (129,2.102e-03) (321,5.874e-04) (769,1.623e-04) (1793,4.442e-05) (4097,1.207e-05) (9217,3.261e-06) }; 
%\addplot coordinates{ (7,8.472e-02) (31,3.044e-02) (111,1.022e-02) (351,3.303e-03) (1023,1.039e-03) (2815,3.196e-04) (7423,9.658e-05) (18943,2.873e-05) (47103,8.437e-06) }; 
%\addplot coordinates{ (9,7.881e-02) (49,3.243e-02) (209,1.232e-02) (769,4.454e-03) (2561,1.551e-03) (7937,5.236e-04) (23297,1.723e-04) (65537,5.545e-05) (178177,1.751e-05) }; 
%\addplot coordinates{ (11,6.887e-02) (71,3.177e-02) (351,1.341e-02) (1471,5.334e-03) (5503,2.027e-03) (18943,7.415e-04) (61183,2.628e-04) (187903,9.063e-05) (553983,3.053e-05) }; 
%\addplot coordinates{ (13,5.755e-02) (97,2.925e-02) (545,1.351e-02) (2561,5.842e-03) (10625,2.397e-03) (40193,9.414e-04) (141569,3.564e-04) (471041,1.308e-04) (1496065,4.670e-05) }; 
%\legend{$GAC$,$MaxRPWC1$,$MaxRPWC3$,$rPIC$,$RPWC$} 
%\end{loglogaxis} 
%\end{tikzpicture}
%\end{frame}

%------------------------------------------------
%
%\begin{frame}
%\frametitle{Expérimentation}
%
%\end{frame}
%
%%------------------------------------------------
%
%%------------------------------------------------
%\section{Perspective}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Perspective}
%
%\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{problem} http://www.cril.univ-artois.fr/lecoutre/benchmarks.html
\end{thebibliography}
}
\end{frame}

%%------------------------------------------------
%
%\begin{frame}
%\Huge{\centerline{The End}}
%\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 